#include <iostream>
#include <cassert>
using namespace std;
// 142.环形链表II
// 给你一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x): val(x), next(nullptr) {}
    ListNode(int x,ListNode* next):val(x),next(next) {}
};

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        // 空链表，只有一个结点且没有环的链表，直接返回nullptr
        if(head == nullptr || head->next == nullptr)
            return nullptr;
        ListNode* slow,*fast;
        slow = fast = head;
        bool flag = false;  // 是否有环的标志
        // 首先找到在环中的相遇点
        while(fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
            if(slow == fast) {  //有环，找到首次相遇点
                flag = true;
                break;
            }
        }
        //if(fast == nullptr) {   // 说明链表没有环
        if(flag == false) {
            return nullptr;
        }
        // 从链表头结点开始，从首次相遇结点开始，开始遍历
        ListNode* p1 = head, *p2 = slow;
        while(p1 != p2) {
            p1 = p1->next;
            p2 = p2->next;
        }
        assert(p1 == p2);
        return p1;
    }
};

int main() {
    // 给定链表 1，表示1个元素，无环
    ListNode* node5 = new ListNode(1);
    ListNode* firstMeet = Solution().detectCycle(node5);
    if(firstMeet != nullptr)
        cout << firstMeet->val << endl;

    // 给定链表 1->2->1，pos = 0
    ListNode* node6 = new ListNode(1);
    ListNode* node7 = new ListNode(2);
    node6->next = node7; node7->next = node6;
    firstMeet = Solution().detectCycle(node6);
    if(firstMeet != nullptr)
        cout << firstMeet->val << endl;

    // 给定链表 3->2->0->-4->2，返回索引1
//    ListNode* node4 = new ListNode(-4);
//    ListNode* node3 = new ListNode(0,node4);
//    ListNode* node2 = new ListNode(2,node3);
//    ListNode* node1 = new ListNode(3,node2);
//    node4->next = node2;
//
//    firstMeet = Solution().detectCycle(node1);
//    cout << firstMeet->val << endl;





    return 0;
}
